class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int len = 0;
        for (auto& e : nums) {
            if (e == 1)
                len++;
        }
        int n = nums.size() + len, size = nums.size();
        int ret = 100000000, sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (nums[i % size]);
            if (i >= len)
                sum -= nums[(i - len) % size];
            if (i + 1 >= len) {
                ret = min(ret, len - sum);
                // cout << ret << ' '<<sum<<endl;
            }
            // cout << sum<<' ';
        }
        return ret;
    }
};
class Solution {
public:
    int minFlips(string s) {
        int len = s.size();
        string target = "01";
        int cnt = 0;
        for(int i = 0;i < len;i++){
            cnt += (s[i] == target[i%2]);
        }
        int ret = 0;  ret = max(cnt, len -cnt);
        for(int i = 0; i < len;i++){
            cnt -= (s[i] == target[i%2]);
            cnt += (s[(i + len)%len] == target[(i+len)%2]);
            ret = min({ret,cnt,len - cnt});
            // cout << cnt<<' ';
        }
        return ret;
    }
};
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> map_s1(26), map_s2(26);
        for (auto e : s1)
            map_s1[e - 'a']++;
        int k = s1.size();
        for (int i = 0; i < s2.size(); i++) {
            map_s2[s2[i] - 'a']++;
            if (i >= k)
                map_s2[s2[i - k] - 'a']--;
            if (map_s2[s2[i] - 'a'] == map_s1[s2[i] - 'a']) {
                bool t = true;
                for (int i = 0; i < 26; i++) {
                    if (map_s1[i] != map_s2[i]) {
                        t = false;
                        break;
                    }
                }
                if (t == true)
                    return true;
            }
        }
        return false;
    }
};
vector<int> s_map,p_map;
bool fun(string& s, string& p,int pos){
    for(int i = 0; i < 26;i ++){
        if(s_map[i] != p_map[i])  return false; 
    }
    return true;//p != s.substr(pos,p.size());
}
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        s_map = vector<int>(26);
        p_map = vector<int>(26);
        for(auto e : p)  p_map[e - 'a']++;
        int k = p.size();
        vector<int>ret;
        for(int i = 0;i < s.size();i++){
            s_map[s[i] - 'a']++;
            if(i >= k) s_map[s[i - k] - 'a']--;

            if(s_map[s[i] - 'a'] == p_map[s[i] - 'a'])
            {
                if(fun(s,p,i))   ret.push_back(i - p.size() + 1);
            }
        }
        return ret;
    }
};

bool cmp(vector<int>& v1, vector<int>& v2) {
    for (int i = 0; i < 26; i++) {
        if (v1[i] != v2[i])
            return false;
    }
    return true;
}
bool fun(const string& str, vector<string> words) {
    int len = words[0].size();
    vector<string> vs;
    for (int i = 0; i < str.size(); i += len) {
        vs.emplace_back(str.substr(i, len));
    }
    sort(vs.begin(),vs.end());
    for(int i = 0; i < words.size();i++){
        if(vs[i] != words[i])
            return false;
    }
    return true;
}
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        sort(words.begin(),words.end());
        vector<int> ret;
        vector<int> vv(26);
        int k = words.size() * words[0].size();
        for (auto e : words) {
            for (auto ee : e)
                vv[ee - 'a']++;
        }
        vector<int> s_vv(26);
        for (int i = 0; i < s.size(); i++) {
            s_vv[s[i] - 'a']++;
            if (i >= k)
                s_vv[s[i - k] - 'a']--;
            if (i + 1 >= k && s_vv[s[i] - 'a'] == vv[s[i] - 'a'] ) {
                if(i + 1 != k &&s_vv[s[i - k] - 'a'] != vv[s[i - k] - 'a'])
                    continue;
                if (cmp(vv, s_vv)) {
                    // 字母相等
                    if (fun(s.substr(i - k + 1, k), words))
                        ret.push_back(i - k + 1);
                }
            }
        }
        return ret;
    }
};
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int m = words.size(), n = words[0].size(), ls = s.size();
        for (int i = 0; i < n && i + m * n <= ls; i++) {
            unordered_map<string, int> differ;
            for (int j = 0; j < m; j++) {
                ++differ[s.substr(i + n * j, n)];
            }
            for (string& word : words) {
                if (--differ[word] == 0)
                    differ.erase(word);
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    string word =
                        s.substr(start + (m - 1) * n, n); // 窗口右边加的单词
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    // 移除窗口左侧移出的单词
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
                    ret.emplace_back(start);
                }
            }
        }
        return ret;
    }
};